package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.PrinterUtils;

import java.util.ArrayList;
import java.util.List;

public class GreedySearch extends HeuristicSearch{

    private int nodeNum = 0;

    public GreedySearch(Problem problem) {
        super(problem);
        this.nodeNum = problem.getNodeNum();
    }

    public void solve() {
        Solution solution = search();
        PrinterUtils.printTspResult("greedy", solution);
    }

    public Solution search(){
        int i = 0;
        List<Integer> solution = new ArrayList<>();
        solution.add(i);
        while (solution.size() < nodeNum) {
            int[] next = new int[nodeNum];
            for (int k = 0; k < nodeNum; k++) {
                next[k] = distance[i][k];
            }

            int j = selectNearestNeighborhood(next, solution);
            solution.add(j);
            i = j;
        }
        return new Solution(solution, calculateFitness(solution));
    }

    private int selectNearestNeighborhood(int[] distance, List<Integer> solution) {
        int bestValue = Integer.MAX_VALUE;
        int bestIndex = 0;
        for (int i = 0; i < distance.length; i++) {
            if (!solution.contains(i)) {
                if (distance[i] < bestValue) {
                    bestValue = distance[i];
                    bestIndex = i;
                }
            }
        }
        return bestIndex;
    }


}
